package com.heima.algorithm.dynamicprogramming;

import java.util.Arrays;
import java.util.List;

/**
 * 完全背包问题，区别于0-1背包问题，可以重复选择物品
 * @author 勾新杰
 * @version 1.0
 * @date 2024/11/11 8:20
 */
public class KnapsackProblemComplete {
    /*
        编号    名称        重量(g)     价值(元)
         0      青铜c         2            3
         1      黄金a         4            7
         2      白银s         3            4

            0   1   2   3   4   5   6
         0  0   0   c   c   cc  cc  ccc
         1  0   0   c   c   a   a   ac
         2  0   0   c   s   a   a   ac

         其中dp[i,j]表示用用前0-i个物品组合背包容量为j时能装下的最大价值，
         与0-1背包问题不同的在于选择了当前物品，还可以再次选择当前物品

         if(装不下){
            dp[i,j] = dp[i-1][j]
         }else{
            dp[i,j] = max(dp[i-1][j], currItem.value + dp[i][j - currItem.weight])
         }
     */

    /**
     * 物品类
     */
    public static class Item {
        int index;
        String name;
        double weight;
        double value;

        public Item() {
        }

        public Item(int index, String name, double weight, double value) {
            this.index = index;
            this.name = name;
            this.weight = weight;
            this.value = value;
        }

        public double valuePerWeight() {
            return value / weight;
        }

        public String name() {
            return name;
        }

        public double value() {
            return value;
        }

        @Override
        public String toString() {
            return "{" +
                    "name='" + name + '\'' +
                    ", weight=" + weight +
                    ", value=" + value +
                    '}';
        }
    }

    /**
     * 选择最大价值
     * @param itemList 物品列表
     * @param totalWeight 总重量
     * @return  选择结果的最大价值
     */
    public static double select(List<Item> itemList, double totalWeight) {
        // 1. 准备dp二维数组
        int rows = itemList.size();
        int columns = (int) (totalWeight + 1);
        double[][] dp = new double[rows][columns];
        // 2. 对dp数组第一行进行初始化
        for (int j = 0; j < columns; j++) {
            if (itemList.get(0).weight <= j){
                dp[0][j] = itemList.get(0).value + dp[0][j - (int) itemList.get(0).weight]; // 剩下看能不能用当前物品继续dou出来最大价值
            }
        }
        print(dp);
        // 3. 逐行遍历dp数组，计算dp[i][j]
        for (int i = 1; i < rows; i++) {
            Item currItem = itemList.get(i);
            for (int j = 0; j < columns; j++) {
                if (j < currItem.weight){
                    dp[i][j] = dp[i - 1][j];
                }else {
                    dp[i][j] = Math.max(dp[i - 1][j], currItem.value + dp[i][(int) (j - currItem.weight)]); // 前0 - i个物品去dou剩下的背包空间的最大价值
                }
            }
            print(dp);
        }
        // 4. 返回dp数组右下角
        return dp[rows - 1][columns - 1];
    }

    /**
     * 打印dp数组
     * @param dp dp数组
     */
    private static void print(double[][] dp) {
        for (double[] ints : dp) {
            System.out.print("[ ");
            for (double anInt : ints) {
                System.out.printf("%02d ", (int)anInt);
            }
            System.out.println("]");
        }
        System.out.println();
    }

    /**
     * 选择最大价值，dp数组降为一维
     * @param itemList 物品列表
     * @param totalWeight 总重量
     * @return  选择结果的最大价值
     */
    public static double select2(List<Item> itemList, double totalWeight) {
        // 1. 准备dp一维数组
        double[] dp = new double[(int) (totalWeight + 1)];
        // 2. 对dp数组第一行进行初始化
        // 3. 逐行遍历dp数组，计算dp[i][j]
        for (Item currItem : itemList) {
            for (int j = 0; j < dp.length; j++) {
                if (currItem.weight <= j) {
                    dp[j] = Math.max(dp[j], currItem.value + dp[(int) (j - currItem.weight)]); // 前0 - i个物品去dou剩下的背包空间的最大价值
                }
            }
            System.out.println(Arrays.toString(dp));
        }
        // 4. 返回dp数组右下角
        return dp[dp.length - 1];
    }

    public static void main(String[] args) {
        Item item1 = new Item(1, "青铜c", 2, 3);
        Item item2 = new Item(2, "黄金a", 4, 7);
        Item item3 = new Item(3, "白银s", 3, 4);
        List<Item> itemList = List.of(item1, item2, item3);
        double totalWeight = 6;
        double result = select(itemList, totalWeight);
        System.out.println(result);
        result = select2(itemList, totalWeight);
        System.out.println(result);
    }
}
